#ifndef __LINKEDLIST__
#define __LINKEDLIST__
#include <iostream>

using namespace std;

template <typename Element>
class Node{
	public:
		Node():next(NULL) {}
		Node(const Element & item):data(item),next(NULL){}
		Element data;
		Node * next;
};

template <typename Element>
class LinkedList{
	typedef Node<Element> * NodePtr;
	unsigned size;
	NodePtr head;
	Node<Element>& Back();
	Node<Element>& Front();
public:
	LinkedList():size(0),head(NULL){}
	LinkedList(const LinkedList& other);
	LinkedList& operator=(const LinkedList& other);
	~LinkedList();
	bool IsEmpty() const;
	unsigned Size() const;
	void PushBack(Node<Element>& item);
	void PushFront(Node<Element>& item);
	void Insert(int pos, Node<Element>& item);
	void Delete(int pos);
	void Debug();
};


template <typename Element>
inline bool LinkedList<Element>::IsEmpty() const{
	return size==0;
}

template <typename Element>
inline unsigned LinkedList<Element>::Size() const{
	return size;
}

template <typename Element>
void LinkedList<Element>::Debug(){
	NodePtr first = head;
	while(first!= NULL){
		cout<< first->data << " ";
		first = first->next;
	}
	cout<<endl;
}

template <typename Element>
Node<Element>& LinkedList<Element>::Front(){
	return *head;
}

template <typename Element>
Node<Element>& LinkedList<Element>::Back(){
	if(this->IsEmpty()) return *head;
	Node<Element> * Back = head ;
	while(Back->next != NULL){
		Back = Back->next;
	}
	return *Back;
}

template <typename Element>
void LinkedList<Element>::PushBack(Node<Element> & item){
	if(this->IsEmpty()){
		head = & item;
		++size;
	}else{
		this->Back().next = &item;
		++size;
	}
}

template <typename Element>
void LinkedList<Element>::PushFront(Node<Element> & item){
	if(this->IsEmpty()){
		head = & item;
		++size;
	}else {
		item.next = head;
		head = & item;
		++size;
	}
}

template <typename Element>
void LinkedList<Element>::Insert(int pos,Node<Element>& item){
	if(pos<0 || pos >size) return;
	if(pos == 0) {
		this->PushFront(item);
	}else if(pos == size){
		this->PushBack(item);
	}else {
		Node<Element>* nptr = head;
		for(int i=0; i< pos-1; ++i){
			nptr = nptr->next;
		}
		item.next = nptr->next;
		nptr->next = &item;
		++size;
	}
}

template <typename Element>
void LinkedList<Element>::Delete(int pos){
	if(pos<0 || pos >size) return;
	if(pos==0){
		if(this->IsEmpty()) return;
		NodePtr del = head->next;
		head = del;
		--size;
	}else {
		NodePtr befor = head;
		for(int i=0;i<pos-1;++i){
			befor = befor->next;
		}
		befor->next = befor->next->next;
		--size;
	}
}

template <typename Element>
LinkedList<Element>::~LinkedList(){
	size = 0;
}

#endif